package com.atguigu.algorithm;

public class CoinProblem02 {
    public static int minCoin(int[] arr,int aim){
        return process(0,5,arr);
    }
    public static int process(int index,int rest,int[] arr){
        //rest为剩余量
        if(rest<0){ //说明此时已经超过目标值aim了
            return -1;
        }
        if(rest==0){ //刚好，我们就返回0
            return 0;
        }
            if(index==arr.length){
                return -1; //此时也不可能
            }else{
                int p1=process(index+1,rest,arr);
                int p2=process(index+1,rest-arr[index],arr);
                if(p1==-1 && p2==-1){
                    return -1;
                }else{
                    if(p1==-1){
                        return  p2;
                    }
                    if(p2==-1){
                        return p1;
                    }
                    return Math.min(p1,p2+1);
                }
            }
    }
}
